package com.lwt.codetop.backtracking;

// 93. 复原 IP 地址

import java.util.ArrayList;
import java.util.List;

/**
 * 思路：划分行子集型回溯，注意剪枝即可:
 *                              n >= 4
 *                              拆分出来的子串长度 <= 12（四个255）
 *                              划分的子集个数为4个
 *                              每个数的范围在[0~255]
 *                              不能含有前导0
 */
public class RestoreIPAddresses {
    private static List<String> res = new ArrayList<>();
    private static int n;
    private static String s;
    public static void main(String[] args) {
        s = "25525511135";
        n = s.length();
        if (n <= 3) {
            System.out.println("非法序列");
        }
        dfs(0, 0, 0, "");
        System.out.println(res);
    }

    private static void dfs(int u, int start, int cnt, String curs) {
        if(u == n){
            if(cnt == 4){
                res.add(curs.substring(0, curs.length() - 1));
            }
            return;
        }
        // 不选: u < n - 1，当到最后一位时，必须要选
        if(u < n - 1) dfs(u + 1, start, cnt, curs);
        // 选 + 剪枝
        String t = s.substring(start, u + 1);
        Long num = Long.parseLong(t); // 为了防止越界这样用Long类型
        if(t.length() > 12) return;
        if(cnt > 4) return;
        if(num > 255) return;
        if(t.length() > 1 && t.charAt(0) == '0') return;
        dfs(u + 1, u + 1, cnt + 1, curs + t + '.');
    }
}
